package leetcode.calc._06_07;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 * <p>
 * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 * <p>
 * 此外，你可以假设该网格的四条边均被水包围。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：grid = [
 * ['1','1','1','1','0'],
 * ['1','1','0','1','0'],
 * ['1','1','0','0','0'],
 * ['0','0','0','0','0']
 * ]
 * 输出：1
 * 示例 2：
 * <p>
 * 输入：grid = [
 * ['1','1','0','0','0'],
 * ['1','1','0','0','0'],
 * ['0','0','1','0','0'],
 * ['0','0','0','1','1']
 * ]
 * 输出：3
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/number-of-islands
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _06_28_143_重排链表 {
    public static void main(String[] args) {
        Solution sol = new _06_28_143_重排链表().new Solution();
        if (true) {
            ListNode head = crtNode(1, 2, 3, 4);
            sol.reorderList(head);
        }
    }

    private static ListNode crtNode(int ...args) {
        ListNode head = new ListNode(args[0]);
        ListNode tmp = head;
        for (int i = 1; i < args.length; i++) {
            tmp.next = new ListNode(args[i]);
            tmp = tmp.next;
        }
        return head;
    }

    static public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    class Solution {
        public void reorderList(ListNode head) {
            // 创建一个List
            List<ListNode> list = new ArrayList<>();
            ListNode tmp = head.next;
            if (tmp != null) {
                list.add(tmp);
                tmp = tmp.next;
            }
            if (list.size() < 2) {
                return;
            }
            int start = 0;
            int last = list.size() - 1;
            tmp = head;
            while (last > start) {
                tmp.next = list.get(last);
                tmp = tmp.next;
                tmp.next = list.get(start);
                tmp = tmp.next;
                start++;
                last--;
            }
            if (start != last) {
                start = last;
            }
            ListNode node = list.get(start);
            tmp.next = node;
            node.next = null;
        }
    }
}
